package com.mj.listen2._01_排序.cmp;

import java.util.ArrayList;
import java.util.List;

/**
 * 希尔排序
 */
public class _08_HillSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        List<Integer> shellStpSequence = shellStpSequence();
        for (int step : shellStpSequence) {
            // 针对某个步长进行插入排序
            sort(step);
        }
    }

    private void sort(int step) {
        // 在空间上想象成列。col: 第几列, column的简称
        for (int col = 0; col < step; col++) {
            for (int begin = col + step; begin < array.length; begin += step) {
                int curIndex = begin;
                while (curIndex > col && cmp(curIndex, curIndex - step) < 0) {
                    swap(curIndex, curIndex - step);
                    curIndex -= step;
                }
            }
        }
    }

    /**
     * 希尔本人提出的步长序列
     */
    private List<Integer> shellStpSequence() {
        List<Integer> shellSteps = new ArrayList<>();
        int step = array.length;
        // step = (step >> 1)
        while ((step >>= 1) > 0) {
            // 收集步长
            shellSteps.add(step);
        }
        return shellSteps;
    }
}
